#include <stdio.h>
#include <random>

#include "BSTree.h"
int binarySearch(int nums[], int len, int target, int &cnt){
    int left = 0, right = len - 1, mid;
    cnt = 0;
    while(left <= right){
        cnt++;
        mid = left + (right - left) / 2;
        if(nums[mid] == target){
            return mid;
        }else if(target > nums[mid]){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return -1;
}

void question1(){
    int nums[80];
    nums[0] = 0;
    for(int i = 1; i < 80; i++){
        nums[i] = nums[i - 1] +  rand() % 10 + 1;
    }
    for(int i = 0; i < 80; i++){
        printf("%d\t", nums[i]);
        if((i+1) % 10 == 0){
            printf("\n");
        }
    }
    int cnt;
    int index = binarySearch(nums, 80, 400, cnt);
    if(index != -1){
        printf("查找次数：%d\n", cnt);
    }else{
        printf("未找到！\n");
    }
}

void question2(){
    BSTree root;
    int n = 10;
    int val;
    while(n--){
        printf("输入：");
        scanf("%d", &val);
        insert(root, val);
    }
    inorder(root);
}

void insertSort(int nums[100]){
    int cnt = 0;
    int i, j;
    for(i = 1; i < 100; i++){
        int temp = nums[i];
        j = i - 1;
        while(j >= 0 && temp < nums[j]){
            cnt++;
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = temp;
    }
    printf("直接插入排序比较次数：%d\n", cnt);
}
void shellSort(int nums[], int len){
    int cnt = 0;
    for(int interval = len / 2; interval > 0; interval /= 2){
        for(int i = interval; i < len; i++){
            int target = nums[i];
            int j = i - interval;
            while(j >= 0 && target < nums[j]){
                cnt++;
                nums[j + interval] = nums[j];
                j -= interval;
            }
            nums[j + interval] = target;
        }
    }
    printf("希尔排序比较次数：%d\n", cnt);
}
void quickSort(int nums[100], int begin, int end, int &cnt){
    if(begin < end){
        int e = nums[begin];
        int left = begin + 1, right = end;
        while(left <= right){
            while(left <= right && nums[left] <= e) {
                cnt++;
                left++;
            }
            while(left <= right && nums[right] > e) {
                cnt++;
                right--;
            }
            if(left < right){
                cnt++;
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        nums[begin] = nums[right];
        nums[right] = e;
        quickSort(nums, begin, right - 1, cnt);
        quickSort(nums, right + 1, end, cnt);
    }
}
void mergeSort(int nums[100], int begin, int end, int &cnt){
    if(begin < end){
        int mid = begin + (end - begin) / 2;
        mergeSort(nums, begin, mid, cnt);
        mergeSort(nums, mid + 1, end, cnt);
        //合并
        int help[100];
        for(int i = begin; i <= end; i++) help[i] = nums[i];
        int cur = begin;
        int left = begin, right = mid + 1;
        while(left <= mid && right <= end){
            if(help[left] <= help[right]){
                nums[cur++] = help[left++];
            }else{
                nums[cur++] = help[right++];
            }
            cnt++;
        }
        while(left <= mid) nums[cur++] = help[left++];
    }
}
void question3(){
    int len = 100;
    int nums[len];
    for(int i = 0; i < len; i++){
        nums[i] = rand() % 1000;
    }
    int nums1[len], nums2[len], nums3[len], nums4[len];
    for(int i = 0; i < len; i++){
        nums1[i] = nums2[i] = nums3[i] = nums4[i] =nums[i];
    }
    printf("排序前：\n");
    for(int i = 0; i < len; i++){
        printf("%d\t", nums1[i]);
        if((i + 1) % 10 == 0)
            printf("\n");
    }
    insertSort(nums1);
    shellSort(nums2, 100);
    int cnt = 0;
    quickSort(nums3, 0, 99, cnt);
    printf("快速排序比较次数：%d\n", cnt);
    cnt = 0;
    mergeSort(nums4, 0, 99, cnt);
    printf("归并排序比较次数：%d\n", cnt);

    printf("排序后：\n");
    for(int i = 0; i < len; i++){
        printf("%d\t", nums4[i]);
        if((i + 1) % 10 == 0)
            printf("\n");
    }
}
int main(){
    // question1();
    // question2();
    question3();
    return 0;
}